# 青蛙跳台阶问题
# 每次只跳一级或者两级，求跳n级有多少种跳法
class Solution:
    def climbStairs(self, n):
        a=1
        b=2
        res=a+b
        if n==1:
            return 1
        if n==2:
            return 2
        for i in range(3,n+1):
            res=a+b
            a=b
            b=res
        return res

# 可以跳1级，2级至n级，问跳上n级有多少种跳法
def Jump12n(n):
    if n==1:
        return 1
    else:
        return 2*Jump12n(n-1)

# 可以跳1级，2级至m级，问跳上n级有多少种跳法
def Jump12m(n,m):
    if n>m:
        return 2*Jump12m(n-1,m)-Jump12m(n-1-m,m)
        


def main():
    n=6
    # sol=Solution()
    # res=sol.climbStairs(n)
    # print(res)
    res=Jump12n(n)
    print(res)

main()